package code1.binary_tree;


import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;

/**
 * 原题链接：https://leetcode.cn/problems/symmetric-tree/
 */
public class P101 {

    //判断二叉树是否对称
    public boolean isSymmetric(TreeNode root) {
        Queue<TreeNode> queue=new LinkedList<>();
        queue.offer(root.left);
        queue.offer(root.right);
        while(!queue.isEmpty()){
            TreeNode leftNode = queue.poll();
            TreeNode rightNode = queue.poll();
            if(leftNode==null && rightNode==null){
                continue;
            }
            if(leftNode==null || rightNode==null || leftNode.val!=rightNode.val){
                return false;
            }
            queue.offer(leftNode.left);
            queue.offer(rightNode.right);
            queue.offer(leftNode.right);
            queue.offer(rightNode.left);
        }
        return true;
    }

    //比较两子树是否镜像对称
    public boolean compare(TreeNode leftNode,TreeNode rightNode){
        if(leftNode==null && rightNode==null) return true;
        if(leftNode==null && rightNode!=null) return false;
        if(leftNode!=null && rightNode==null) return false;
        if(leftNode.val != rightNode.val) return false;

        //两节点不为空且值相等
        boolean flag1 = compare(leftNode.left, rightNode.right);
        boolean flag2 = compare(leftNode.right, rightNode.left);
        return flag1 && flag2;
    }

    public boolean isSymmetric2(TreeNode root) {
        if(root==null){
            return true;
        }
        boolean result = compare(root.left, root.right);
        return result;
    }





    //使用双端队列
    public boolean isSymmetric3(TreeNode root) {
        Deque<TreeNode> deque=new LinkedList<>();
        deque.add(root.left);
        deque.add(root.right);
        while(!deque.isEmpty()){
            TreeNode leftNode = deque.getFirst();
            TreeNode rightNode = deque.getLast();
            if(leftNode==null && rightNode==null){
                continue;
            }
            if(leftNode==null || rightNode==null || leftNode.val!=rightNode.val){
                return false;
            }
            deque.addFirst(leftNode.right);
            deque.addLast(rightNode.left);
            deque.addFirst(leftNode.left);
            deque.add(rightNode.right);
        }
        return true;
    }
}
